243. Shortest Word Distance
Easy

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

 

Constraints:

  • 1 <= wordsDict.length <= 3 * 104
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.
  • word1 != word2
Accepted
134,680
Submissions
215,083
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.75 (52 votes)

Premium

Solution

This is a straight-forward coding problem. The distance between any two positions i1i_1 and i2i_2 in an array is i1i2|i_1 - i_2|. To find the shortest distance between word1 and word2, we need to traverse the input array and find all occurrences i1i_1 and i2i_2 of the two words, and check if i1i2|i_1 - i_2| is less than the minimum distance computed so far.


Approach #1 (Brute Force)

Algorithm

A naive solution to this problem is to go through the entire array looking for the first word. Every time we find an occurrence of the first word, we search the entire array for the closest occurrence of the second word.

Complexity Analysis

The time complexity is O(n2)O(n^2), since for every occurrence of word1, we traverse the entire array in search for the closest occurrence of word2.

Space complexity is O(1)O(1), since no additional space is used.


Approach #2 (One-pass)

Algorithm

We can greatly improve on the brute-force approach by keeping two indices i1 and i2 where we store the most recent locations of word1 and word2. Each time we find a new occurrence of one of the words, we do not need to search the entire array for the other word, since we already have the index of its most recent occurrence.

Complexity Analysis

  • Time complexity: O(NM)O(N \cdot M) where NN is the number of words in the input list, and MM is the total length of two input words.

  • Space complexity: O(1)O(1), since no additional space is allocated.


Report Article Issue

Comments: 21
niksite's avatar
Read More

You do not need currentDistance here.

67
Show 1 reply
Reply
Share
Report
Mr-Programmer's avatar
Read More

Once we find the minDistance to be equal to 1, we can just return because it can never go down below that. This will help in saving some time as well if the first two words itself are word1 and word2.

31
Reply
Share
Report
Suralin's avatar
Read More

Don't need either currentDistance or to keep track of both indices:

min_dist = len(words)
curr_word, idx = None, 0
for i, w in enumerate(words):
    if w not in (word1, word2): continue
    if curr_word and w != curr_word:
        min_dist = min(min_dist, i - idx)
    curr_word, idx = w, i
return min_dist

15
Show 1 reply
Reply
Share
Report
weijinwang's avatar
Read More

Check words[i] is word1 or word2, else continue. This can save a little.

5
Reply
Share
Report
marinak2003's avatar
Read More

Why the 2nd approach has Time complexity: O(N⋅M) and not O(N)? Why "the total length of two input words." influences the time complexity here?

7
Show 6 replies
Reply
Share
Report
Mrmagician's avatar
Read More

My python submission

out = first = second = float('inf')
        for i,word in enumerate(words):
            if word == word1: first = i
            elif word == word2: second = i
            out = min(abs(first - second), out)
        return out

6
Reply
Share
Report
chandan16's avatar
Read More

This easy question in interview will turn into a super hard problem by maintaining list of indices for each word and performing a binary search and so on :-)

2
Reply
Share
Report
softwareshortcut's avatar
Read More

Just for fun, here is a more robust solution if we consider a few more edge cases (word 1 or word 2 are not in the list, etc).

    public int shortestDistance(String[] words, String word1, String word2) {
        if ((words == null) || (words.length == 0)) 
            return -1;
        
        int index_w1=-1, index_w2=-1;
        int shortestDistance = Integer.MAX_VALUE;
        for (int i=0; i<words.length; i++) {
            if (words[i].equals(word1))
                index_w1 = i;            
            if (words[i].equals(word2))
                index_w2 = i;
            
            // We found a new path between w1 and w2
            if ((index_w1!=-1) && (index_w2!=-1)) {
                shortestDistance = Math.min(shortestDistance, Math.abs(index_w1-index_w2));
            }            
        }
        
        return shortestDistance == Integer.MAX_VALUE? -1 : shortestDistance;
    }

2
Reply
Share
Report
SherMM's avatar
Read More

def shortestDistance(self, words, word1, word2):
    """
    :type words: List[str]
    :type word1: str
    :type word2: str
    :rtype: int
    """
    shortest = len(words)+1
    index = None
    found = None
    for i, word in enumerate(words):
        if word == word1 or word == word2:
            if found is not None:
                if word != found:
                    shortest = min(shortest, i - index)
            found = word
            index = i
    return shortest

2
Reply
Share
Report
jaumard's avatar
Read More

There an error for the one pass solution minDistance = Math.min(minDistance, Math.abs(i1 - i1)); have to be minDistance = Math.min(minDistance, Math.abs(i1 - i2));

1
Show 1 reply
Reply
Share
Report
Success
Details
Runtime: 8 ms, faster than 91.57% of C++ online submissions for Shortest Word Distance.
Memory Usage: 11.5 MB, less than 99.74% of C++ online submissions for Shortest Word Distance.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/16/2021 09:29Accepted8 ms11.5 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.